package com.dily.study.demo.struct.demo;

import lombok.Data;

import java.util.List;
import java.util.concurrent.atomic.AtomicReference;

/**
 * Date: 2022-10-09 星期日
 * Time: 13:56
 * Author: Dily_Su
 * Remark: 二叉树节点
 */
@Data
public class TreeNode<T> {
    // 父节点
    private TreeNode<T> parent;
    // 左节点
    private TreeNode<T> left;
    // 右节点
    private TreeNode<T> right;
    // 该节点的层次/深度
    private Integer deep;
    // 数据
    private T data;

    public TreeNode(T data) {
        this.data = data;
    }

    /**
     * 获取节点的最后一个可用节点
     *
     * @param node 树
     * @return 非空的可用节点
     */
    public static TreeNode<?> getLast(TreeNode<?> node) {

        if (node.left == null || node.right == null) {
            return node;
        }
        TreeNode<?> leftNode = getLast(node.left);
        TreeNode<?> rightNode = getLast(node.right);
        if (leftNode.deep > rightNode.deep) {
            return rightNode;
        }
        return leftNode;
    }

    public void addNode(TreeNode<?> root, TreeNode<T> node) {
        TreeNode<T> next = (TreeNode<T>) getLast(root);
        if (next.getLeft() == null) {
            next.setLeft(node);
            next.getLeft().setDeep(next.getDeep() + 1);
            return;
        }
        if (next.getRight() == null) {
            next.setRight(node);
            next.getRight().setDeep(next.getDeep() + 1);
        }
    }

    /**
     * 根据List 创建二叉树
     *
     * @param list 数组
     * @return 二叉树
     */
    public TreeNode<T> createTree(List<T> list) {
        AtomicReference<TreeNode<T>> root = new AtomicReference<>();

        list.forEach(e -> {
            if (root.get() == null) {
                root.set(new TreeNode<>(e));
                root.get().setDeep(1);
            } else
                addNode(TreeNode.getLast(root.get()), new TreeNode<T>(e));
        });

        return root.get();
    }

    /**
     * 先序遍历
     * 先当前节点，然后左节点，最后右节点
     *
     * @param node 节点
     */
    public static void preOrder(TreeNode<?> node) {
        if (node != null) {
            System.out.println(node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    /**
     * 中序遍历
     * 先左节点，然后当前节点，最后右节点
     *
     * @param node 节点
     */
    public static void middleOrder(TreeNode<?> node) {
        if (node != null) {
            middleOrder(node.left);
            System.out.println(node.data);
            middleOrder(node.right);
        }
    }

    /**
     * 后序遍历
     * 先左节点，然后右节点，最后当前节点
     *
     * @param node 节点
     */
    public static void postOrder(TreeNode<?> node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.data);
        }
    }

}
